// https://www.lintcode.com/problem/house-robber/description

class Solution {
public:
    /**
     * @param A: An array of non-negative integers
     * @return: The maximum amount of money you can rob tonight
     */
    long long houseRobber(vector<int> &A) {
        // 线性DP题目.

        // 设 dp[i] 表示前i家房子最多收益, 答案是 dp[n], 状态转移方程是

        // dp[i] = max(dp[i-1], dp[i-2] + A[i-1])
        // 考虑到dp[i]的计算只涉及到dp[i-1]和dp[i-2], 因此可以O(1)空间解决.
        
        // 个
        // long long result = 0;
        // long long p = 0;
        // for (int i = 0; i < A.size(); ++i)
        // {
        //     long long tmp = result;
        //     result = max(result, A[i] + p);
        //     p = tmp;
        // }
        // return result;
        long long result = 0;
        long long f = 0, g = 0, f1 = 0, g1 = 0;
        int len = A.size();
        for (int i = 0; i < len; i++) {
            f1 = g + A[i];
            g1 = max(f, g);
            g = g1, f = f1;        
        }
        return max(g, f);
    }
};